1. Field of the Invention
The present invention relates to a data transforming technique capable of lossless transformation of nth-order integer data into nth-order integer data in a lossless orthogonal transform essential for transforming image data of each block and processing lossless coding and lossy coding by a unified scheme, in order to particularly implement various kinds of lossless rotational transforms which form the lossless orthogonal transform.
2. Description of the Related Art
An image, especially a multi-valued image, includes many pieces of information, and requires a huge memory capacity for storage and a lot of time for transmission. The storage and transmission of an image uses high-efficiency coding to reduce the amount of data by removing redundancy of the image or changing its contents to a level at which the deterioration of image quality is visually unrecognizable.
For example, JPEG, which is recommended by ISO and ITU-T as an international standard coding scheme for still images, transforms image data of each block (8×8 pixels) into a DCT coefficient by executing a discrete cosine transform (DCT). JPEG quantizes each coefficient and entropy-encodes the quantized coefficient, compressing the image data. Other compression techniques using the DCT are H.261 and MPEG-1/2/4 in addition to JPEG.
In the JPEG standard, lossless coding was also standardized to make a compressed/decompressed image completely match an original image. In those days, studies of lossless transform techniques did not make remarkable progress, and a lossless transform using the DCT could not be implemented. Lossless coding was therefore performed not by block transform coding using the DCT but by predictive coding of each pixel.
Later, an international standard (JPEG-LS) dedicated to lossless coding of still images was established. However, in this standard lossless transform technique was not used. The JPEG 2000 using a lossless wavelet transform for lossless image coding became an international standard later on. The lossless wavelet transform is a lossless transform from an integer data set to an integer data set. Coding using a lossless transform can literally achieve lossless coding unless the transmission coefficient is quantized. The intervention of quantization processing enables lossy coding. That is, this coding can seamlessly perform lossless coding and lossy coding by the same transform scheme. With this advantage, coding using the lossless transform is adopted even in JPEG-XR, which is now being internationally standardized.
One conventional technique for achieving a lossless transform uses ladder calculations (lifting calculations). A typical example of this method is described in Shinji Fukuma, Koichi Ohyama, Masahiro Iwahashi, and Noriyoshi Kambayashi, “Lossless 8-Point Fast Discrete Cosine Transform Using Lossless Hadamard Transform”, IEICE technical report, IE99-65, pp. 37-44, October 1999. In this reference, the lossless transform is implemented by complicated procedures of decomposing a transform matrix into triangular matrices and replacing them with ladder calculations. Therefore, this arrangement is complex and requires a large amount of calculation processing.
Japanese Patent Laid-Open No. 2003-258645 discloses a lossless transform method limited to the Hadamard transform. The method disclosed in this reference rounds up the fractional parts of an odd number of data and rounds down those of another odd number of data for transform coefficients of fractional data obtained by a linear Hadamard transform. This reference has a feature in the rounding method, and does not devise to reduce calculations of the linear Hadamard transform or decrease the amount of processing necessary for round processing.
As described above, conventional lossless transform techniques need to perform redundant processing by ladder calculations in order to attain reversibility. This obstructs high-speed lossless coding and lossy coding using a lossless transform.